import java.util.*;
public class Test {
    /*
    题目 1： 两数之和
     */
    public int[] twoSum (int[] numbers, int target) {
        Map<Integer, Integer> map = new HashMap<>();

        for(int i = 0; i < numbers.length; i++){
            if(map.containsKey(target -  numbers[i])){
                return new int[]{map.get(target - numbers[i]) + 1, i + 1};
            }else{
                map.put(numbers[i], i);
            }
        }
        return null;
    }

    /*
    题目 2：数组中出现次数超过一半的数字
     */
    public int MoreThanHalfNum_Solution(int [] array) {
        // 候选法
        if(array.length <= 2){
            return array[0];
        }

        int x = array[0];
        int sum = 1;

        for(int i = 1; i < array.length; i++){
            if(sum == 0){
                x = array[i];
                sum = 1;
            }else{
                if(x == array[i]){
                    sum++;
                }else{
                    sum--;
                }
            }
        }
        return x;
    }

    /*
    题目 3：数组中只出现一次的两个数字
     */
    //异或 可以看成是无进制相加！
    public int[] FindNumsAppearOnce (int[] array) {
        int temp = 0;
        int res1 = 0;
        int res2 = 0;
        for(int i = 0; i < array.length; i++){
            temp ^= array[i];
        }

        int k = 1;

        while((temp & k) == 0){
            k <<= 1;
        }

        // 分组
        for(int i = 0; i < array.length; i++){
            if((k & array[i]) == 0){
                res1 ^= array[i];
            }else{
                res2 ^= array[i];
            }
        }

        if(res1 < res2){
            return new int[]{res1, res2};
        }else{
            return new int[]{res2, res1};
        }
    }

    /*
    题目 4：缺失的第一个正整数
     */
    public static int minNumberDisappeared (int[] nums) {
        int n = nums.length;
        for(int i = 0; i < n; i++){
            while(nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1]){
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }

        for(int i = 0; i < n; i++){
            if(nums[i] != i + 1){
                return i + 1;
            }
        }

        return n + 1;
    }

    public static void main1(String[] args) {
        int[] arr = {3,4,-1,1};
        int ret = minNumberDisappeared(arr);
        System.out.println(ret);
    }

    /*
    题目 5：斐波那契数列
     */
    public int Fibonacci(int n) {
        if(n <= 2){
            return 1;
        }

        int a = 1;
        int b = 1;
        int c = 0;

        while((n - 2) > 0){
            c = a + b;
            a = b;
            b = c;
            n--;
        }

        return c;
    }
}
